package com.gitee.jsbd.algorithm.sort;

import java.util.Arrays;

/**
 * 桶排序 O(n)
 * 工作原理：
 * 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。
 * 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
 * 当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（O（n））。
 * 但桶排序并不是比较排序，他不受到 O(nlogn) 下限的影响。
 */
public class BucketSort {

    public static void bucketSort(int[] data) {//data为待排序数组
        int n = data.length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) { // 计算待排序数组的最大值
            max = data[i] > max ? data[i] : max;
        }

        int[] buckets = new int[max + 1];
        for (int i = 0; i < n; i++) {
            buckets[data[i]]++;
        }

        int c = 0;
        for (int j = 0; j < max + 1; j++) {
            while (buckets[j]-- > 0) {
                data[c++] = j;
            }
        }

    }

    public static void main(String[] args) {
        // 排序前数组
        int[] data = new int[]{5, 8, 7, 9, 1, 2, 3, 8, 2, 1, 0, 10, 11, 44, 5};
        System.out.print("==初始化==：");
        System.out.println(Arrays.toString(data));

        bucketSort(data);
        System.out.println(Arrays.toString(data));
    }

}
